\chapter{数据结构}
\section{二叉树的概念}
\begin{definition}[二叉树]
	二叉树由节点的有限集合构成，这个有限集合或者为空集 (empty)或者为由一个根结点 (root) 及两棵互不相交、分别称作这个根的左子
	树 (left subtree) 和右子树 (rightsubtree) 的二叉树组成的集合
\end{definition}
二叉树可以是空集合,因此根可以有空的左子树或右子树或者左右子树皆为空。
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{binary_tree}
	\caption{树}
\end{figure}
\begin{definition}[节点]
	\begin{itemize}
		\item 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
		\item 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
		\item 兄弟节点：具有相同父节点的节点互称为兄弟节点。
		\item 没有子树的节点称为叶子节点。
		\item 非终端节点称为分支节点。
	\end{itemize}
\end{definition}

\begin{definition}[边]
	两个节点的有序对称为边。
\end{definition}
\begin{definition}[路径]
	除了根节点$k_0$外的任何节点$k\in K$都存在一个节点序列$k_0,k_1,\cdots,k_s$使得$k_0$就是树根，且$k_s = k$，其中有序对$<k_{i-1},k_i>\in r(1\leq i\leq s)$这样的节点序列称为从根到节点k的一条路径，路径长度为s（包含的边数）
\end{definition}
\begin{definition}[祖先，后代]
	若有一条由k到达$k_s$的路径，则称k为$k_s$的祖先，$k_s$是k的子孙。
\end{definition}
\begin{definition}[层数]
	根为第0层，其它节点的层数等于其父节点的层数加上1。
\end{definition}
\begin{definition}[深度]
	层数最大的叶节点的层数。
\end{definition}
\begin{definition}[高度]
	层数最大的叶子节点的程序加上1。
\end{definition}
\begin{definition}[满二叉树]
	如果一棵二叉树的任何结点、树叶、恰有两棵非空子树，则此二叉树称作满二叉树。
\end{definition}
\begin{figure}
	\centering
	\includesvg[width=0.5\textwidth]{full_binary_tree}
	\caption{满二叉树}
\end{figure}
\begin{definition}[完全二叉树]
	最多只有最下面的两层结点度数可以小于2，最下一层的结点都集中最左边。
\end{definition}
\begin{figure}
	\centering
	% \includegraphics[width=0.5\textwidth]{tree5}
	\includesvg[width=0.5\textwidth]{complete_binary_tree}
	\caption{完全二叉树}
\end{figure}
\begin{definition}[扩充二叉树]
	所有空子树,都增加空树叶， 外部路径长度E和内部路径长度I， 满足:$E=I+2n$(n是内部结点个数)。
\end{definition}
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{extend_binary_tree}
	\caption{扩充二叉树}
\end{figure}
\begin{itemize}
	\item [性质1] 在二叉树中,第i层上最多有 $2^i$个结点($i\geq 0$)
	\item [性质2] 深度为 k 的二叉树至多有$2^{k+1}-1$个结点($k\geq$)，其中深度(depth)定义为二叉树中层数最大的叶结点的层数
	\item [性质3] 一棵二叉树,若其终端结点数为 $n_0$ ,度为2的结点数为 $n_2$ ,则 $n_0 =n_2 +1$
	\item [性质4] 满二叉树定理:非空满二叉树树叶数目等于其分支结点数加1
	\item [性质5] 满二叉树定理推论:一个非空二叉树的空子树数目等于其结点数加1
	\item [性质6] 有n个结点(n>0)的完全二叉树的高度为 $\lfloor\log_2 (n+1)\rfloor$ (深度为$\lfloor\log_2(n+1) \rfloor -1$)
\end{itemize}
\section{树结构ADT}
\begin{longlisting}
	\caption{二叉树节点ADT}
	\cudafile[firstline=46,lastline=74]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:banary_node_adt}
\end{longlisting}

\begin{longlisting}
	\caption{二叉树的ADT}
	\cudafile[firstline=16,lastline=44]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:binary_tree_adt}
\end{longlisting}
\section{遍历数据结构}
\subsection{先序遍历}
\emph{先序遍历：先遍历根节点，然后左节点最后右节点。}
\begin{figure}[H]
	\centering
	\includegraphics[width=.5\textwidth]{posTraval}
	\caption{先序遍历[3,9,4,5,7]}
	\label{fig:preTraval}
\end{figure}
\begin{longlisting}
	\caption{先序遍历}
	\cppfile[firstline=2,lastline=20]{third_party/coding/cxx/algorithm/datastruct/src/preorderTraversal.cc}
	\label{code:perOrder}
\end{longlisting}

\subsection{后序遍历}
\emph{后序遍历：先遍历左节点，然后右节点最后根节点。}
\begin{figure}[H]
	\centering
	\includegraphics[width=.5\textwidth]{posTraval}
	\caption{后序遍历[9,5,7,4,3]}
	\label{fig:posTraval}
\end{figure}
递归版后序遍历：
\begin{longlisting}
	\caption{后序遍历}
	\cppfile[firstline=2,lastline=18]{third_party/coding/cxx/algorithm/datastruct/src/postorderTraversal.cc}
	\label{code:postTraval}
\end{longlisting}

\subsection{中序遍历}
\emph{中序遍历：先遍历左节点，然后根节点最后右节点。}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{posTraval}
	\caption{中序遍历[9,3,5,4,7]}
	\label{fig:inTraval}
\end{figure}
\begin{longlisting}
	\caption{中序遍历（递归实现）}
	\cppfile[firstline=420,lastline=442]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:inorderTraversal}
\end{longlisting}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{inorderTraversalStack}
	\caption{中序遍历递归实现示意图}
	\label{fig:inorderTraversalStack}
\end{figure}
\figref{fig:inorderTraversalStack}通过栈实现中序遍历算法：
\begin{enumerate}
	\item 初始化栈。
	\item 如果当前节点不为空或者栈不为空则：
		\begin{itemize}
			\item 将当前节点和所有左子节点加入栈。
		\end{itemize}
	\item 将栈中元素出栈同时将当前节点的右节点入栈。然后回到第二步再次判断。
\end{enumerate}
迭代实现中序遍历：
\begin{longlisting}
	\caption{中序遍历（迭代实现）}
	\cppfile[firstline=691,lastline=706]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:inorderTraversalD}
\end{longlisting}
\subsection{BFS}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.4\textwidth]{bfs_tree}
	\caption{树的BFS遍历}
	\label{fig:bfs_tree}
\end{figure}
\subsection*{BFS非递归实现}
\begin{example}[实现宽度优先搜索遍历]
	\begin{figure}[H]
		\centering
		\includegraphics[width=0.5\textwidth]{bfs_travel}
		\caption{宽度优先搜索}
	\end{figure}
\end{example}
\begin{longlisting}
	\caption{宽度优先搜索实现}
	\cppfile[firstline=3,lastline=29]{third_party/coding/cxx/algorithm/datastruct/src/BFSTravelBinaryTree.cc}
	\label{code:removeDuplicateLetters}
\end{longlisting}

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{bfs_tree_queue}
	\caption{树的BFS遍历（非递归）}
	\label{fig:bfs_tree_queue}
\end{figure}
BFS的非递归处理：
\emph{如果根节点不为空将根节点加入队列，然后如果队列不为空则节点出队，拿到节点的值然后将节点的左右子节点（不为空）加入队列，直到队列为空为止}。
\subsection{DFS}
DFS搜索函数的重要组成部分：
\begin{itemize}
	\item 节点（递归调用的时候使用不同的节点递归访问）
	\item 是否访问(告诉函数某一个节点是否访问)
	\item 搜索图（这个图不一定是真正的图，可以是二维的邻接矩阵，也可以是邻接表等，图在代码中不会变动）
\end{itemize}
DFS通常用来遍历整个图或者树，但是使用DFS的目的通常为了通过遍历所有可能性求出需要了解的节点组合或者最小路径长度之类的结果，所以调用DFS后处理才是问题的关键。DFS递归调用结束表示给定节点能访问的可能性都访问完了，如果是为了获取图的可访问数目，这时候只需要添加计数即可找到所有能访问的节点组合。DFS实现有两种方式：
\begin{enumerate}
	\item 递归方式。
	\item 非递归方式。
\end{enumerate}
对于\figref{fig:dfs_tree}的树：
\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth]{dfs_tree}
	\caption{树的DFS遍历（递归）}
	\label{fig:dfs_tree}
\end{figure}
递归方式遍历整棵树的流程：访问根节点（1），如果根节点不为空递归访问根节点的左节点和右节点，直到节点左右子节点为空为止。非递归方式流程如\figref{fig:dfs_tree_stack}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{dfs_tree_stack}
	\caption{树的DFS遍历（非递归）}
	\label{fig:dfs_tree_stack}
\end{figure}
非递归访问方式：
\begin{enumerate}
	\item 如果根节点不为空，将根节点入栈。
	\item 出栈，遍历节点内容。同时将当前节点的右节点和左节点入栈。
\end{enumerate}
DFS非递归方式访问模板：
\begin{cpp}
boolean DFS(int root,int target){
  set<Node> visitor;//当前节点是否访问过
  stack<Node> s;
  s.add(root);//根节点入栈
  while(!s.empty()){
    Node current = s.top();//获取栈顶节点
    if(current == target)//这里的条件根据具体访问有所不同
    return true;
    for(auto current_node:current_nodes){//current_nodes为current连接的节点列表
      if(visitor.count(current_node)!=0){// 如果节点列表中的节点没有被访问过
        s.push(current_node);//将节点入栈
        visitor.add(current_node);//标记当前节点已经访问过
      }
    }
    s.pop(current);
  }
  return false;
}
\end{cpp}
\subsection{遍历二叉树}
\begin{itemize}
	\item 系统地访问数据结构中的节点
	\item 每个节点都正好被访问一次
\end{itemize}
常见的二叉树遍历：
\begin{itemize}
	\item 先序遍历：访问根节点，左子树，右子树
	\item 中序遍历：访问左子树 ，根节点，右子树
	\item 后序遍历：左子树，右子树，根节点
\end{itemize}
\begin{figure}
	\centering
	\includesvg[width=0.5\textwidth]{simple_tree}
	\caption{树的遍历}
	\label{fig:simple_tree}
\end{figure}
\figref{fig:simple_tree}不同遍历的结果：
\begin{itemize}
	\item 先序遍历：A B D E G C F H I
	\item 中序遍历：D B G E A C H F I
	\item 后序遍历：D G E B H I F C A
\end{itemize}
深度优先遍历二叉树
\begin{cpp}
template<class T>
void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root)
{
  if(root!=nullptr){
    Visit(root);
    DepthOrder(root->leftchild())://先序遍历
    DepathOrder(root->rightcgild());//递归访问右子树
}
}
\end{cpp}
\subsection{迭代实现先序遍历二叉树}
\begin{itemize}
	\item 遇到一个结点,就访问该结点,并把此结点的非空右结点推入栈中,然后下降去遍历它的左子树;
	\item 遍历完左子树后,从栈顶弹出一个结点,并按照它的右链接指示的地址再去遍历该结点的右子树结构。
\end{itemize}
\begin{longlisting}
	\caption{先序遍历迭代实现}
	\cudafile[firstline=92,lastline=108]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:preorderTraversal_adt}
\end{longlisting}

\subsection{迭代实现中序遍历二叉树}
\begin{itemize}
	\item  遇到一个结点
	      \begin{itemize}
		      \item 把它推入栈中
		      \item 遍历其左子树
	      \end{itemize}
	\item 遍历完左子树
	      \begin{itemize}
		      \item 从栈顶弹出该结点并访问之
		      \item 按照其右链地址遍历该结点的右子树
	      \end{itemize}
\end{itemize}
\begin{longlisting}
	\caption{二叉树的中序遍历迭代实现}
	\cudafile[firstline=130,lastline=145]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:binary_tree_inorder_adt}
\end{longlisting}
\subsection{非递归后序遍历二叉树}
\begin{itemize}
	\item 给栈中元素加上一个特征位
	      \begin{itemize}
		      \item Left表示已进入该节点的左子树，将从左边回来
		      \item Right 表示已进入该节点的右子树，将从右边回来
	      \end{itemize}
\end{itemize}
\begin{longlisting}
	\caption{后序遍历二叉树(迭代实现)}
	\cudafile[firstline=163,lastline=189]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:postorderTraversalStack}
\end{longlisting}
各种遍历算法的时间复杂度分析：
\begin{itemize}
	\item 在各种遍历中，每个节点都被访问且只被访问一次，时间复杂度为$O(n)$。
	\item 非递归保存出入栈（或者队列）时间
	      \begin{itemize}
		      \item 先序，中序，某些节点出入栈一次，不超过$O(n)$。
		      \item 后续，每个节点分别从左，右边各入出一次，$O(n)$。
	      \end{itemize}
\end{itemize}
深搜：栈的深度和树的高度有关，最好$O(logn)$,最坏$O(n)$。
\subsection{宽度优先遍历二叉树}
从二叉树的第 0 层(根结点)开始,自上至下 逐层遍历;在同一层中,按照 从左到右 的顺序对结点逐一访问。
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{travel_layer_binary_tree}
	\caption{宽度优先遍历}
\end{figure}
遍历结果为：A B C D E F G H I。
\begin{longlisting}
	\caption{层序遍历}
	\cudafile[firstline=191,lastline=205]{third_party/coding/cxx/datastruct/tree/include/binary_tree_node.hpp}
	\label{code:level_order}
\end{longlisting}
在各种遍历中,每个结点都被访问且只被访问一次,时间复杂度为$O(n)$非递归保存入出栈(或队列)时间,宽搜,正好每个结点入/出队一次,$O(n)$宽度优先搜索：与树的最大宽度有关，最好$O(1)$最坏$O(n)$。
\textbf{二叉树的链式存储结构}\\*
二叉链表：指针left和right分别指向节点的左孩子和右孩子。
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{binary_link_node}
	\caption{二叉链表}
\end{figure}
三叉链表：指针left和right，分别指向节点的左孩子和右孩子，增加一个父指针
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{three_link_node}
	\caption{三叉链表}
\end{figure}
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{binary_link_tree}
	\caption{二叉链表表示的树}
\end{figure}
指向父母的指针parent。
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{three_link_node_tree}
	\caption{三叉链表表示的树}
\end{figure}
在BinaryTreeNode类中添加两个私有数据成员
\begin{cpp}
private:
BinaryTreeNode<T> *left;  // 指向左子树的指针
BinaryTreeNode<T> *right; // 指向右子树的指针
template <class T> class BinaryTreeNode {
friend class BinaryTree<T>;  // 声明二叉树类为友元类
private:
  T info;  // 二叉树结点数据域
public:
  BinaryTreeNode(); // 缺省构造函数
  BinaryTreeNode(const T& ele);  // 给定数据的构造
  BinaryTreeNode(const T& ele, BinaryTreeNode<T> *l,
  BinaryTreeNode<T> *r); // 子树构造结点
}
\end{cpp}
递归框架寻找父节点：
\begin{cpp}
template<class T>
BinaryTreeNode<T>* BinaryTree<T>::
Parent(BinaryTreeNode<T> *rt, BinaryTreeNode<T> *current) {
  BinaryTreeNode<T> *tmp,
  if (rt == nullptr) return(NULL);
  if (current == rt ->leftchild() || current == rt->rightchild())
    return rt; // 如果孩子是current则返回parent
  if ((tmp =Parent(rt- >leftchild(), current) != nullptr)
    return tmp;
  if ((tmp =Parent(rt- > rightchild(), current) != nullptr)
    return tmp;
  return nullptr;
}
\end{cpp}
非递归框架找父节点：
\begin{cpp}
BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current) {
  using std::stack;  // 使用STL中的栈
  stack<BinaryTreeNode<T>* > aStack;
  BinaryTreeNode<T> *pointer = root;
  aStack.push(nullptr);  // 栈底监视哨
  while (pointer) {  // 或者!aStack.empty()
  if (current == pointer->leftchild() || current == pointer->rightchild())
    return pointer;  // 如果pointer的孩子是current则返回parent
  if (pointer->rightchild() != nullptr)  // 非空右孩子入栈
    aStack.push(pointer->rightchild());
  if (pointer->leftchild() != nullptr)
    pointer = pointer->leftchild();  // 左路下降
  else {    // 左子树访问完毕,转向访问右子树
    pointer=aStack.top(); aStack.pop(); // 获得栈顶元素,并退栈
} } }
\end{cpp}
空间开销分析：
\begin{itemize}
	\item 存储密度$\alpha(\leq 1)$比啊是数据结构存储的效率。\[\alpha(\text{存储密度}=\frac{\text{数据本身存储量}}{\text{整个结构占用的存储总量}})\]
	\item 结构性开销$\gamma=1-\alpha$
\end{itemize}
\textbf{空间开销}
根据满二叉树定义：一般的指针是空的。每个节点存两个指针，一个数据域：
\begin{itemize}
	\item 总空间$（2p+d）n$
	\item 结构性开销:$2pn$
	\item 如果p = d,则结构性开销2p(2p+d) = 2/3
\end{itemize}
C++ 可以用两种方法来实现不同的分支与叶结点:
\begin{itemize}
	\item  用union联合类型定义
	\item  使用C++的子类来分别实现分支结点与叶结点,并采用虚函数isLeaf来区别分支结点与叶结点
\end{itemize}
早期节省内存资源
\begin{itemize}
	\item  利用结点指针的一个空闲位(一个bit)来标记结点所属的类型
	\item 利用指向叶的指针或者叶中的指针域来存储该叶结点的值
\end{itemize}
\textbf{顺序方法存储二叉树}\\*
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{binary_tree_sequence}
	\caption{二叉树的顺序存储}
\end{figure}
\begin{itemize}
	\item 把节点按一定的顺序存储到一片连续的存储单元。
	\item 使节点在序列中的位置反映出相应的结构信息。
\end{itemize}
存储结构上是线性的，逻辑结构上它让然是二叉树形结构。
从节点的编号就可以推知其父母，孩子，兄弟的编号
\begin{itemize}
	\item 当 $2i+1<n$ 时,结点 i 的左孩子是结点 $2i+1$,否则结点i没有左孩子
	\item 当 $2i+2<n$ 时,结点 i 的右孩子是结点 $2i+2$,否则结点i没有右孩子
\end{itemize}
完全二叉树的下标公式：
\begin{itemize}
	\item 当 0<i<n 时,结点 i 的父亲是结点 $\lfloor(i-1)\rfloor$
	\item 当 i 为偶数且 0<i<n 时,结点 i 的左兄弟是结点 i-1，否则结点 i 没有左兄弟。
	\item 当 i 为奇数且 i+1<n 时,结点i的右兄弟是结点 i+1,否则结点i没有右兄弟。
\end{itemize}
\textbf{二叉搜索树}\\*
\begin{figure}[H]
	\centering
	% \includegraphics[width=0.5\textwidth]{tree13}
	\includesvg[width=0.5\textwidth]{binary_search_tree}
	\caption{二叉搜索树}
\end{figure}
\begin{definition}[二叉搜索树（Binary Search Tree(BST)）]
	或者是一棵空树或者是具有如下性质的二叉树：
	\begin{itemize}
		\item 对于任何一个节点，设其值为K则：该节点的左子树（若不空）的任意一个节点的值都小于K。该节点的右子树（若不空）的任意一个节点的值都大于K，而且他的左右子树也分别是BST。
	\end{itemize}
\end{definition}
性质：中序遍历是正序的（由小到大排列）。
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{binary_tree_delete}
	\caption{二叉树的删除}
\end{figure}
\begin{cpp}
void BinarySearchTree<T>:::removehelp(BinaryTreeNode <T> *& rt, const T val) {
if (rt==nullptr) 
  cout<<val<<" is not in the tree.\n";
else if (val < rt->value())
  removehelp(rt->leftchild(), val);
else if (val > rt->value())
  removehelp(rt->rightchild(), val);
else {    // 真正的删除
	BinaryTreeNode <T> * temp = rt;
	if (rt->leftchild() == nullptr) rt = rt->rightchild();
	else if (rt->rightchild() == nullptr) rt = rt->leftchild();
	else {
		temp = deletemin(rt->rightchild());
		rt->setValue(temp->value());
	}
	delete temp;
}
}
\end{cpp}
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{tree5}
	\caption{删除右子树最小节点}
\end{figure}
找右子树中最小节点，并删除。
\begin{cpp}
template <class T>
BinaryTreeNode* BST::deletemin(BinaryTreeNode <T> *& rt) {
  if (rt->leftchild() != nullptr)
    return deletemin(rt->leftchild());
  else { 
    // 找到右子树中最小,删除
    BinaryTreeNode <T> *temp = rt;
    rt = rt->rightchild();
    return temp;
  }
}
\end{cpp}
二叉搜索树是适用于内存储器的一种重要的树形索引，常用红黑树、伸展树等,以维持平衡外存常用B/B+树。
\subsection{堆的定义和实现}
\begin{figure}
	\centering
	\includesvg[width=.5\textwidth]{heap_construct}
	\caption{堆的实现}
\end{figure}
\begin{definition}[最小堆]
	$K_0,K_1,\cdots,K_{n-1}$具有如下特性：
	\begin{itemize}
		\item $K_i\leq K_{2i+1}(i=0,1,\ldots,\lfloor n/2\rfloor-1)$
		\item $K\leq K_{2i+2}$
	\end{itemize}
\end{definition}
堆的性质：
\begin{itemize}
	\item 完全二叉树的层次序列，可以使用数组表示。
	\item 堆中存储的数据是局部有序的，堆部位以。节点的值和其孩子的值之间存在限制。任何一个节点和其兄弟之间都没有直接的限制。
	\item 从逻辑的角度看，堆实际上是一种树形结构。
\end{itemize}
\begin{cpp}
template <typename T>
class MinHeap {  // 最小堆ADT定义
private:
	T* heapArray;  // 存放堆数据的数组
	int CurrentSize; // 当前堆中元素数目
	int MaxSize;  // 堆所能容纳的最大元素数目
	void BuildHeap();  // 建堆
public:
	MinHeap(const int n);  // 构造函数,n为最大元素数目
	virtual ~MinHeap(){delete []heapArray;};  // 析构函数
	bool isLeaf(int pos) const;  // 如果是叶结点,返回TRUE
	int leftchild(int pos) const;  // 返回左孩子位置
	int rightchild(int pos) const;  // 返回右孩子位置
	int parent(int pos) const;  // 返回父结点位置
	bool Remove(int pos, T& node);   // 删除给定下标的元素
	bool Insert(const T& newNode);  // 向堆中插入新元素newNode
	T& RemoveMin();  // 从堆顶删除最小值
	void SiftUp(int position);  // 从position向上开始调整,使序列成为堆
	void SiftDown(int left);  // 筛选法函数,参数left表示开始处理的数组下标
}
\end{cpp}
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{tree17}
	\caption{对最小堆用筛选法}
\end{figure}
\begin{cpp}
template <class T>
void MinHeap<T>::SiftDown(int position) {
	int i = position;  // 标识父结点
	int j = 2*i+1;  // 标识关键值较小的子结点
	Ttemp = heapArray[i]; // 保存父结点
	while (j < CurrentSize) {
			if((j < CurrentSize-1)&&
			(heapArray[j] > heapArray[j+1]))
			j++;  // j指向数值较小的子结点
			if (temp > heapArray[j]) {
					heapArray[i] = heapArray[j];
					i = j;
					j = 2*j + 1;    // 向下继续
				}
			else break;
		}
	heapArray[i]=temp;
}
\end{cpp}
对最小堆用shiftup向上调整：
\begin{cpp}
template<class T>
void MinHeap<T>::SiftUp(int position) {
  // 从position向上开始调整,使序列成为堆
  int temppos=position;
  // 不是父子结点直接swap
  T temp=heapArray[temppos];
  while((temppos>0) && (heapArray[parent(temppos)] > temp)) {
  heapArray[temppos]=heapArray[parent(temppos)];
  temppos=parent(temppos);
  }
  heapArray[temppos]=temp;// 找到最终位置
}
\end{cpp}
建最小堆的过程：
首先,将 n 个关键码放到一维数组中
\begin{itemize}
	\item 整体不是最小堆
	\item 所有叶结点子树本身是堆 当 $i \geq\lfloor n/2 \rfloor$时,以关键码 K i 为根的子树已经是堆。
	\item 从倒数第二层,$i=\lfloor n/2 \rfloor$-1开始从右至左依次调整
	\item 直到整个过程到达树根,整棵完全二叉树就成为一个堆。
\end{itemize}
建最小堆：从第一个分支结点 heapArray[CurrentSize/2-1]开始,自底向上逐步把以子树调整成堆。
\begin{cpp}
template<class T>
void MinHeap<T>::BuildHeap()
{
	// 反复调用筛选函数
	for (int i=CurrentSize/2-1; i>=0; i--)
	    SiftDown(i);
}
\end{cpp}
最小堆插入新元素：
\begin{cpp}
template <class T>
bool MinHeap<T>::Insert(const T& newNode)
//向堆中插入新元素newNode
{
  if(CurrentSize==MaxSize)  // 堆空间已经满
  return false;
  heapArray[CurrentSize]=newNode;
  SiftUp(CurrentSize);  // 向上调整
  CurrentSize++;
}
\end{cpp}
最小堆删除元素操作
\begin{cpp}
template<class T>
bool MinHeap<T>::Remove(int pos, T& node) {
if((pos<0)||(pos>=CurrentSize))
  return false;
T temp=heapArray[pos];
heapArray[pos]=heapArray[--CurrentSize];
if (heapArray[parent(pos)]> heapArray[pos])
  SiftUp(pos);    //上升筛
else 
  SiftDown(pos); // 向下筛
node=temp;
return true;
}
\end{cpp}
堆的效率分析：\\*
n 个结点的堆,高度 $d = \lfloor log 2 n + 1\rfloor$ 。根为第 0 层,则第 i 层结点个数为 $2^i$,
考虑一个元素在堆中向下移动的距离 。
\begin{itemize}
	\item 大约一半的结点深度为 d-1,不移动(叶)。
	\item 四分之一的结点深度为 d-2,而它们至多能向下移动一层。
	\item 树中每向上一层,结点的数目为前一层的一半,而子树高度加一。因而元素移动的最大距离的总数为$\sum_{i=1}^{\log n}(i-1)\frac{n}{2^i}=O(n)$
\end{itemize}
最小堆操作效率：\\*
建堆算法时间复杂度为O(n)，堆有log n层深，插入节点，删除普通元素和删除最小元素的平均时间复杂度和最差时间复杂度都是O(log n)

堆可以用于实现优先队列:
\begin{itemize}
	\item 优先队列，1.根据需要释放具有最小(大)值的对象。2. 最大树、 左高树HBLT、WBLT、MaxWBLT
	\item 改变已存储于优先队列中对象的优先权。 辅助数据结构帮助找到对象
\end{itemize}
\textbf{树的存储实现}
% \cppfile{code/DS/tree/ex2/Tree.h}
% \cppfile{code/DS/tree/ex2/Tree.cpp}
% \cppfile{code/DS/tree/ex2/main.cpp}
\textbf{树的链表实现}

节点的头文件定义
% \cppfile{code/DS/tree/ex3/Node.hpp}
节点的实现
% \cppfile{code/DS/tree/ex3/Node.cc}
树的头文件定义：
% \cppfile{code/DS/tree/ex3/Tree.hpp}
树的实现：
% \cppfile{code/DS/tree/ex3/Tree.cc}
验证代码：
% \cppfile{code/DS/tree/ex3/main.cpp}
\section{表达式二叉树}\label{sec:express_tree}
\begin{definition}[表达式二叉树（Expression Binary Tree）]
是一种特定类型的二叉树，通常用于表达算术表达式或逻辑表达式的解析和计算。它将算术表达式（如加法、减法、乘法、除法等）或逻辑表达式（如与、或、非等）转换为二叉树结构，从而使得表达式能够以树的形式来存储和计算。
\end{definition}
根据表达式类型可以分为：
\begin{itemize}
	\item 前缀表达式二叉树：前缀表达式（波兰表示法）的二叉树表示，其中操作符位于其操作数之前。例如，表达式 + a b 的二叉树中，+ 是根节点，a 和 b 是叶子节点。
	\item 中缀表达式二叉树：中缀表达式（标准数学表示法）的二叉树表示，其中操作符位于其操作数之间。例如，表达式 a + b 的二叉树中，+ 是根节点，a 和 b 是叶子节点。
	\item 后缀表达式二叉树：后缀表达式（逆波兰表示法）的二叉树表示，其中操作符位于其操作数之后。例如，表达式 a b + 的二叉树中，+ 是根节点，a 和 b 是叶子节点。
\end{itemize}
对于一个 3+(2-5)*6/3 表达式，其本身就是中缀表达式。前缀表达式通常需要中缀表达式先转换为后缀表达式然后再转换为前缀表达式。
\begin{itemize}
	\item 前缀表达式：+ 3 / * - 2 5 6 3
	\item 中缀表达式：3 + ( 2 - 5 ) * 6 / 3
	\item 后缀表达式：3 2 5 - 6 * 3 / +
\end{itemize}
\subsection{中缀表达式树}
树的每个节点可以是：
\begin{itemize}
	\item 操作数节点： 包含操作数（例如数字或变量）。这些节点通常是叶子节点。
	\item 运算符节点： 包含运算符（例如 +, -, *, /）。这些节点通常是内部节点。
\end{itemize}
表达式树的结构反映了表达式的运算顺序。

\subsection{中缀表达式转换为后缀表达式}
\begin{itemize}
	\item 初始化一个空栈，用于存储操作符。
	\item 初始化一个空列表（这里只是一个容器，可以用栈或者向量根据实际使用决定），用于存储输出的后缀表达式。
	\item 从左到右扫描中缀表达式：
		\begin{itemize}
			\item 	如果遇到操作数，直接将其添加到输出列表。
	                \item 如果遇到左括号 (，将其压入栈。
	                \item 如果遇到右括号 )，从操作栈中弹出操作符并添加到输出列表，直到遇到左括号 (。
	                \item 如果遇到操作符，根据操作符的优先级和栈顶操作符的优先级决定：
				\begin{itemize}
					\item 如果栈为空，或者栈顶操作符的优先级低于当前操作符，将当前操作符压入栈。
					\item 否则，从栈中弹出操作符并添加到输出列表，直到栈为空或栈顶操作符的优先级低于当前操作符，然后将当前操作符压入栈。
				\end{itemize}
		\end{itemize}
	\item 扫描完成后，将栈中剩余的操作符依次弹出并添加到输出列表。
\end{itemize}
对于表达式：3+(2-5)*6/3，后缀表达式计算过程如下：
\begin{enumerate}
	\item 数字3入表达式栈。
	\item 符号‘+’，入符号栈（当前栈中不存在优先级大于当前符号的操作符号）。
	\item 符号‘(’，直接入符号栈。
	\item 数字2，入表达式栈。
	\item 符号-，入符号栈（当前栈中不存在优先级大于当前符号的操作符号）。
	\item 数字5，入表达式栈。
	\item 符号‘)’，将表达式中符号出栈同时入符号栈，直到遇到‘(’。
	\item 符号‘*’，当前符号操作优先级高于符号栈里面的‘+’，入符号栈。
	\item 数字6，入表达式栈。
	\item 符号‘/’，入符号栈（当前操作符和栈顶元素优先级别相同 ，弹出栈顶元素）。
	\item 将符号栈里面的元素出栈添加到表达式栈。
\end{enumerate}
出入栈流程如\figref{fig:suffix_express}:
\begin{figure}[!htbp]
	\centering
	\includesvg[width=0.5\textwidth]{suffix_express}
	\caption{后缀表达式计算流程}
	\label{fig:suffix_express}
\end{figure}
\subsection{后缀表达式转换为前缀表达式}
算法：
\begin{itemize}
\item 初始化一个空栈。
\item 从左到右扫描后缀表达式。
	\begin{itemize}
		\item 如果遇到操作数，将其压入栈。
		\item 如果遇到操作符，从栈中弹出两个操作数，将操作符放在两个操作数之前，形成一个新的前缀表达式，然后将这个新表达式压入栈。
	\end{itemize}
\item 扫描完成后，栈顶的表达式即为前缀表达式。
\end{itemize}
对于表达式：325-6*3/+，转换为前缀表达式步骤如\figref{fig:prefix_express}。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{prefix_express}
	\caption{后缀表达式转换为前缀表达式}
	\label{fig:prefix_express}
\end{figure}
\subsection{后缀表达式求值}
后缀表达式求值过程如\figref{fig:rpn_eval}。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{rpn_eval}
	\caption{后缀表达式求值过程}
	\label{fig:rpn_eval}
\end{figure}
\subsection{前缀表达式求值}
前缀表达式求值的过程：
\begin{itemize}
\item 初始化一个空栈。
\item 从右到左扫描前缀表达式中的每个元素：
\item 如果是操作数（数字），将其压入栈中。
\item 如果是运算符，从栈中弹出两个元素作为操作数，进行运算，并将结果压回栈中。
\end{itemize}
最后栈中唯一的元素就是计算结果。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{pre_express_eval}
	\caption{前缀表达式计算}
	\label{fig:pre_express_eval}
\end{figure}
\section{Haffman编码}
\subsection{什么是Haffman编码}

\begin{definition}[霍夫曼编码(Huffman Coding)]
\textbf{霍夫曼编码}是一种编码方法，霍夫曼编码是可变字长编码(VLC)的一种。霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
\end{definition}
\subsection{Haffman编码流程}
霍夫曼编码的具体步骤如下：
\begin{itemize}
	\item 将信源符号的概率按减小的顺序排队。
	\item 把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
	\item 画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
	\item 将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
\end{itemize}
\begin{example}[计算haffuman编码]
	现有一个由5个不同符号组成的30个符号的字符串：BABACAC ADADABB CBABEBE DDABEEEBB。
	\begin{table}[H]
		\centering
		\begin{tabular}{ll}
			\toprule
			字符 & 次数 \\
			\midrule
			A  & 8  \\
			B  & 10 \\
			C  & 3  \\
			D  & 4  \\
			E  & 5  \\
			\bottomrule
		\end{tabular}
		\caption{计算字符出现的次数}
	\end{table}
	\begin{enumerate}
		\item 将出现次数最小的两个数3和4相加组合成7。
		      \begin{figure}[H]
			      \centering
			      \includegraphics[width=0.25\textwidth]{haffman_1}
			      \caption{第一步}
		      \end{figure}
		\item 第二步：将最低值5和7组合成12。
		      \begin{figure}[H]
			      \centering
			      \includegraphics[width=0.25\textwidth]{haffman_2}
			      \caption{第二步}
		      \end{figure}
		\item 第三步：将8，10相加组合成18。
		      \begin{figure}[H]
			      \centering
			      \includegraphics[width=0.25\textwidth]{haffman_3}
			      \caption{第三步}
		      \end{figure}
		\item 第四步：最低值12和18相加，结束。
		      \begin{figure}[H]
			      \centering
			      \includegraphics[width=0.5\textwidth]{haffman_4}
			      \caption{第四步}
		      \end{figure}
	\end{enumerate}
	沿着二叉树顶部到每个字符路径获得每个符号的编码。
	\begin{table}[H]
		\centering
		\begin{tabular}{lll}
			\toprule
			字符 & 次数 & 编码  \\
			\midrule
			A  & 8  & 10  \\
			B  & 10 & 11  \\
			C  & 3  & 010 \\
			D  & 4  & 011 \\
			E  & 5  & 00  \\
			\bottomrule
		\end{tabular}
	\end{table}
	我们可以看到出现次数（概率）越多的会越在上层，编码也越短，出现频率越少的就越在下层，编码也越长。当我们编码的时候，我们是按“bit”来编码的，解码也是通过bit来完成，如果我们有这样的bitset “10111101100” 那么其解码后就是 “ABBDE”。所以，我们需要通过这个二叉树建立我们Huffman编码和解码的字典表。

	这里需要注意的是，Huffman编码使得每一个字符的编码都与另一个字符编码的前一部分不同，不会出现像‘A’：00，  ‘B’：001，这样的情况，解码也不会出现冲突。
\end{example}
\begin{remark}
	利用霍夫曼编码，每个符号的编码长度只能为整数，所以如果源符号集的概率分布不是2负n次方的形式，则无法达到熵极限；输入符号数受限于可实现的码表尺寸；译码复杂；需要实现知道输入符号集的概率分布；没有错误保护功能。
\end{remark}
\section{线段树}
线段树也是二叉树，主要用来保存区间$[1,\ldots,N]$和值，这个值根据不同的任务可以为区间的最大值，区间的和，区间元素替换。分解的区间和数n小于4N。一个线段树应该支持的操作包含有：
\begin{enumerate}
	\item update：更新原始输入数据中的某一个值。
	\item query：查询原始输入数据中的对应内容，这个对应内容根据实际情况不同可能是，区间和、区间最小值、区间最大值等等。
\end{enumerate}
构建线段树常见的操作包含：
\begin{itemize}
	\item 子区间划分：对于给定区间[L,R]，只要L < R(直到L=R到达叶子节点) ，线段树就会把它继续分裂成两个区间。首先计算 M = (L+R)/2，左子区间为[L,M]，右子区间为[M+1,R]，然后如果子区间不满足条件就递归分解。	以区间[1-13]的分解为例，分解结果如\figref{fig:construct_seg_tree}。
	\item 子区间合并：如果两个孩子有相同的父节点，用父节点代替两个孩子节点（自底向上）,可以看区间[2,12]=[2]+[3,4]+[5,7]+[8,10]+[11,12]（自底向上）。其中5-7的融合：
		\begin{itemize}
			\item 叶子节点5、6有相同有相同的父节点，用[5-6]节点替代其作为节点。
			\item 5-6节点和7节点有相同的父节点，使用[5-6]节点替代其作为节点。
		\end{itemize}
\end{itemize}
\subsection{线段树的构建}
\figref{fig:construct_seg_tree}展示了线段树的构造过程，通过不断的将原始输入数据2分，然后设置线段树的内容。根节点表示输入数据中数值1-13表示的数值的融合操作，这个操作根据实际用途不同而有所不同。比如如果表示的是区间和则其值是这13个元素的和。如果是区间最大值则表示的是这13个元素的最大值。
\begin{figure}
		\centering
		\includegraphics[width=.7\textwidth]{seg_tree1}
		\caption{线段树区间划分（构造线段树）}
		\label{fig:construct_seg_tree}
\end{figure}
划分区间有两种常见形式，一种是\figref{fig:seg_tree_merge_bt}所示的自底向上划分。另一种则是\figref{fig:seg_tree_merge_tb}展示的自顶向下的划分。
\begin{figure}
	\centering
	\includegraphics[width=.7\textwidth]{seg_tree2}
	\caption{自底向上划分区间}
	\label{fig:seg_tree_merge_bt}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=0.6\textwidth]{seg_tree3}
	\includegraphics[width=0.6\textwidth]{seg_tree4}
	\caption{自顶向下}
	\label{fig:seg_tree_merge_tb}
\end{figure}

\begin{figure}
 	      \centering
 	      \includegraphics[width=0.6\textwidth]{seg_tree5}
		  \caption{计算和（实际数据为[1,2,3,4,1,2,3,4,1,2,3,4,1]）}
\end{figure}

\begin{figure}[H]
   \centering
   \includegraphics[width=0.6\textwidth]{seg_tree6}
   \caption{计算区间和（实际数据为[1,2,3,4,1,2,3,4,1,2,3,4,1]）}
\end{figure}
[1,12]=[2]+[3,4]+[5,7]+[6,10]+[11,12]计算5个数就可以计算出[2,12]的值。
\subsection{线段树的修改值}
修改原始数据之后整个线段树可能需要重新构建。比如我们给原始数组索引2的值修改为10，则这个节点所有的父节点的值都需要根据融合操作修改。如果是区间和则需要线段树此节点上所有的节点的和。
\begin{enumerate}
	\item 自底而上合并规则：
	\item 如何进行区间统计？假设13个数分别是1,2,3,4,1,2,3,4,1,2,3,4,1在区间之后标上的数字为区间内元素的和。
	\item 修改点的值,将数组元素A的第6个数A[6]加上7。
\end{enumerate}
线段树如果采用堆存储则表示的数组的最大范围是$2^{\lfloor logn \rfloor}+1$。因为使用堆存储的数组长度为n，其能表达的二叉树的最大深度为$depth=\lfloor logn \rfloor$，如果是完全二叉树则其节点数为$2^0+2^1+\ldots+2^{depth}=2^{depth+1}-1$。为了计算简单我们通常假设数组长度为4n，因为$\frac{2^{\lfloor logn \rfloor}-1}{n}$的最大值在$n=2^x+1$时得到。此时节点数为$2^{\lfloor logn \rfloor}+1=2^{x+2}-1=4n-5$。
\subsection{线段树ADT}
线段树的ADT如：
\begin{longlisting}
	\caption{线段树的ADT}
	\cudafile[firstline=8,lastline=38]{third_party/coding/cxx/datastruct/tree/include/segment_tree.hpp}
	\label{code:segmentTreeADT}
\end{longlisting}
\begin{longlisting}
	\caption{线段树构建}
	\cudafile[firstline=53,lastline=67]{third_party/coding/cxx/datastruct/tree/include/segment_tree.hpp}
	\label{code:segment_tree_build}
\end{longlisting}
\coderef{code:segment_tree_build}中65行可以根据实际情况使用不同的方案，比如这里是区间求和，如果你想区间求最大值则只需要将代码tree[node] = max(tree[leftChild],tree[rightChild])。线段树构建示意如\figref{fig:segmentTree}，其中红色字符表示的是对应元素的求和，\textcolor{red}{[1-13]}表示的是原始数据中第[0-12]对应元素的求和。有这个是因为构造的线段树根节点起点为1。\textcolor{blue}{[1]}表示此节点在线段树数组中的索引为1。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{segmentTreeQuery}
	\caption{线段树构建示例}
	\label{fig:segmentTree}
\end{figure}

\begin{longlisting}
	\caption{线段树查询}
	\cudafile[firstline=69,lastline=97]{third_party/coding/cxx/datastruct/tree/include/segment_tree.hpp}
	\label{code:segment_tree_build}
\end{longlisting}
query的时候值得注意的是，query(1,4)实际上表示的是对原始数据中的data[0-3]运算，所以query传入的时候会调用内部的递归query，其中start和end用来表示原始数据对应的索引，最开始情况下start=0,end=n-1。以query(1,3)为例说明它是如何计算的（下面）：
\begin{itemize}
	\item query(1,3)按照上面的做法，从根节点树开始（索引为\textcolor{blue}{[1]}为保存data[0-12]的结果），扫描数据的时候从根节点开始，扫描1-13。
	\item 找到当前根节点的左右子节点，并将扫描区间指定到1-7(线段树索引为2)和7-13（索引为3），对1-7继续拆分为1-4和5-7。然后继续对1-4拆分为1-2,3-4。然后对1-2继续拆分为[1,1],[2,2]，此时找到了[2,2]（索引为17下线段树的元素和为2），然后3-4同理为线段树节点9的元素和。然后将结果更新到输出。
\end{itemize}
这样我们就通过线段树找到了2和对应的7，整个求和为9,query(1,3)的结果为9。\coderef{code:segment_tree_insert}线段树的插入和更新：
\begin{longlisting}
	\caption{线段树的插入和更新}
	\cudafile[firstline=99,lastline=130]{third_party/coding/cxx/datastruct/tree/include/segment_tree.hpp}
	\label{code:segment_tree_insert}
\end{longlisting}
\coderef{code:segment_tree_insert}，位置2插入插入元素10：
\begin{itemize}
	\item 初始化扫描区间为0-12。当前起点为根节点，索引为1。
	\item 接着从索引0-6开始查找，然后分成0-3和4-6，接着对0-3分成0-1和[2,2]。此时[2,2]为目标位置，设置对应的值为10。将其更新的[2,2]位置，此时线段树节点为\textcolor{blue}{8}，更新其值为1+10。然后退到其父节点继续更新对应的求和。
\end{itemize}
\section{多叉树}
平衡多分数(Balanced Tree)
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{btree}
	\caption{BTree示意图}
	\begin{definition}[m阶B树]
		\begin{enumerate}
			\item 每个节点至多有m个子节点。
			\item 除根节点和叶子节点外，其它每个节点至少有$\frac{m}{2}$个子节点。
			\item 根节点至少有两个子节点。，为一里外的是根节点就是叶节点的时候没有子节点，此时B树只包含一个节点。
			\item 所有叶节点在统一层。
			\item 所有k个子节点的非根节点恰好包含k-1个关键码。
		\end{enumerate}
	\end{definition}
\end{figure}
\textbf{B树的性质}
\begin{enumerate}
	\item 数高平衡，所有叶子节点都在统一层。
	\item 关键码没有重复，父节点中的关键码是其子节点的分界。
	\item B树把（值接近）相关记录放在同一个磁盘页中，从而利用访问局部性原理。
	\item B树保证树中至少有一定比例的节点是满的。这样能够改进空间里用率，减少检索和更新操作的磁盘读取数目。
\end{enumerate}
B树的节点结构：B树的一个包含j个关键码，j+1个指针的几点的一般形式为：
\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth]{btree_struct}
	\caption{b树的结点结构}
\end{figure}
